// pl/0 compiler with code generation
#include <stdlib.h>
#include <string.h>

#include <math.h>
#include <stdio.h>

#include "pl0.h"

void error(long n){
    long i;

    printf(" ****");
    for (i=1; i<=cc-1; i++){
	printf(" ");
    }
    printf("^%2d\n",n);
    err++; //出错总次数
}

//读取下一个字符
void getch() {
    if(cc==ll)
	{
		if(feof(infile))
		{
			printf("************************************\n");
			printf("      program incomplete\n");
			printf("************************************\n");
			exit(1);
		}
		ll=0; cc=0;
		printf("%5d ", cx);
		while((!feof(infile))&&((ch=getc(infile))!='\n'))
		{
			printf("%c",ch);
			ll=ll+1; line[ll]=ch;
		}
		printf("\n");
		ll=ll+1; line[ll]=' ';
    }
    cc=cc+1; ch=line[cc];
}


//词法分析 sym置成相应类型，经过本过程后 ch 变量中存放的是下一个即将被识别的字符 
void getsym(){
    long i,j,k;
    int flag=0;
    while(ch==' '||ch=='\t'){
	getch();
    }
    if(isalpha(ch)){
	k=0;
	do{
	    if(k<al){
		a[k]=ch; k=k+1;
	    }
	    getch();
	}while(isalpha(ch)||isdigit(ch));
	if(k>=kk){
	    kk=k;
	}else{
	    do{
		kk=kk-1; a[kk]=' ';
	    }while(k<kk);
	}
	strcpy(id,a); i=0; j=norw-1;
	do{
	    k=(i+j)/2;
	    if(strcmp(id,word[k])<=0){
		j=k-1;
	    }
	    if(strcmp(id,word[k])>=0){
		i=k+1;
	    }
	}while(i<=j);
	if(i-1>j){
	    sym=wsym[k];
	}else{
	    sym=ident;
	}
    }else if(isdigit(ch)){
	k=0; num=0; sym=number;
	do{
	    num=num*10+(ch-'0');
	    k=k+1; getch();
	}while(isdigit(ch));
	if(k>nmax){
	    error(31);
	}
    }else if(ch==':'){
	getch();
	if(ch=='='){
	    sym=becomes; getch();
	}else{
	    sym=nul;
	}
    }else if(ch=='<'){
	getch();
	if(ch=='='){
	    sym=leq; getch();
	}else if(ch=='>'){
	    sym=neq; getch();
	}else{
	    sym=lss;
	}
    }else if(ch=='>'){
	getch();
	if(ch=='='){
	    sym=geq; getch();
	}else{
	    sym=gtr;
	}
    }
    else if (ch == '/') {
     		getch();
     		if (ch == '*') {
     			flag++;
     			getch();
     			//用循环计算被注释的代码
     			while (flag > 0) {
     				//直到连续两个字符为“*/”，注释结束 若*后没有/，注释继续
     				while (ch != '*') {
     					getch();
     				}
     				getch();
     				if (ch == '/')
     					flag--;
     			}
     			getch();
     			getsym();//取下一个符号
     		}
     		else {
     			sym = ssym[(unsigned char)'/'];//是除号
     		}
     	}else{
	sym=ssym[(unsigned char)ch]; getch();
    }
}
/* 目标代码生成过程 gen */
//x:要生成的一行代码的助记符* /
//y, z:代码的两个操作数 * /
void gen(enum fct x, long y, long z){
    if(cx>cxmax){
	printf("program too long\n");
	exit(1);
    }
    code[cx].f=x; code[cx].l=y; code[cx].a=z;
    cx=cx+1;
}

///* 测试当前单词是否合法 */   
/* 参数：s1:当语法分析进入或退出某一语法单元时当前单词符合应属于的集合 */   
/*       s2:在某一出错状态下，可恢复语法分析正常工作的补充单词集合 */   
/*       n:出错信息编号，当当前符号不属于合法的 s1 集合时发出的出错信息 */   
void test(__int64 s1, __int64 s2, long n){
    if (!(sym & s1)){
	error(n);
	s1=s1|s2;
	while(!(sym & s1)){
	    getsym();
	}
    }
}


//登记符号表过程// enter object into table
void enter(enum object k){
    tx=tx+1;
    strcpy(table[tx].name,id);
    table[tx].kind=k;
    switch(k){
	case constant:
	    if(num>amax){
		error(31);
		num = 0;
	    }
	    table[tx].val=num;
	    break;
	case variable:
	    table[tx].level=lev; table[tx].addr=dx; dx=dx+1;
	    break;
	case proc:
	    table[tx].level=lev;
	    break;
    }
}

/* 在符号表中查找指定符号所在位置的函数 position */   
/* 参数：id:要找的符号 */   
/* 返回值：要找的符号在符号表中的位置，如果找不到就返回 0 */
long position(char* id){
    long i;

    strcpy(table[0].name,id);
    i=tx;
    while(strcmp(table[i].name,id)!=0){
	i=i-1;
    }
    return i;
}

//常量声明 ident = num
void constdeclaration(){
    if(sym==ident){
	getsym();
	if(sym==eql||sym==becomes){
	    if(sym==becomes){
		error(1);
	    }
	    getsym();
	    if(sym==number){
		enter(constant); getsym();
	    }else{
		error(2);
	    }
	}else{
	    error(3);
	}
    }else{
	error(4);
    }
}


//变量声明处理过程
//var ident
void vardeclaration(){
    if(sym==ident){
	enter(variable); getsym();
    }else{
	error(4);
    }
}

//中间代码生成
//打印 助记符 y z// list code generated for this block
void listcode(long cx0){
    long i;

    for(i=cx0; i<=cx-1; i++){
	printf("%10d%5s%3d%5d\n", i, mnemonic[code[i].f], code[i].l, code[i].a);
    }

}

void expression(__int64);

//因子处理过程
//factor->ident|number|（Exp）
/* 开始因子处理前，先检查当前 token 是否在 facbegsys 集合 中。 */
/* 1 如果这个标识符对应的是常量，值为 val，生成 lit 指令， 把 val 放到栈顶 */
/* 1 如果标识符是变量名，生成 lod 指令， *//* 把位于距离当前层 level 的层的偏移地址为 adr 的变量放到栈顶 */
/* 2 如果是数字生成 lit 指令，把这个数值字面常量放到栈顶 */
/* 3 如果遇到的是左括号 *//* 递归调用 expression 子程序分析一个子表达式 */ 
void factor(__int64 fsys){
    long i;
	
    test(facbegsys,fsys,24);
    while(sym & facbegsys){
	if(sym==ident){
	    i=position(id);
	    if(i==0){
		error(11);
	    }else{
		switch(table[i].kind){
		    case constant:
			gen(lit,0,table[i].val);
			break;
		    case variable:
			gen(lod,lev-table[i].level,table[i].addr);
			break;
		    case proc:
			error(21);
			break;
		}
	    }
	    getsym();
	}else if(sym==number){
	    if(num>amax){
		error(31); num=0;
	    }
	    gen(lit,0,num);
	    getsym();
	}else if(sym==lparen){
	    getsym();
	    expression(rparen|fsys);
	    if(sym==rparen){
		getsym();
	    }else{
		error(22);
	    }
	}
	test(fsys,lparen,23);
    }
}


//term -> factor
/* 每一个项都应该由因子开始，因此调用 factor 子程序分析因子 */
//一个因子后应当遇到乘号或除号 */ 保存
//故调 factor 子程序分析因子 */ 
void term(__int64 fsys){
    __int64 mulop;

    factor(fsys|times|slash);
    while(sym==times||sym==slash){
	mulop=sym; getsym();
	factor(fsys|times|slash);
	if(mulop==times){
	    gen(opr,0,4);
	}else{
	    gen(opr,0,5);
	}
    }
}

//Exp -> +/- term {+term / -term}
void expression(__int64 fsys){
    __int64 addop;


    if(sym==plus||sym==minus){
	addop=sym; getsym();
	term(fsys|plus|minus);
	if(addop==minus){
	    gen(opr,0,1);
	}
    }else{
	term(fsys|plus|minus);
    }
    while(sym==plus||sym==minus){
	addop=sym; getsym();
	term(fsys|plus|minus);
	if(addop==plus){
	    gen(opr,0,2);
	}else{
	    gen(opr,0,3);
	}
    }
}


//条件判断
//cond -> odd exp |exp 大于小于等 exp
void condition(__int64 fsys){
    __int64 relop;

    if(sym==oddsym){
	getsym(); expression(fsys);
	gen(opr,0,6);
    }else{
	expression(fsys|eql|neq|lss|gtr|leq|geq);
	if(!(sym&(eql|neq|lss|gtr|leq|geq))){
	    error(20);
	}else{
	    relop=sym; getsym();
	    expression(fsys);
	    switch(relop){
		case eql:
		    gen(opr,0,8);
		    break;
		case neq:
		    gen(opr,0,9);
		    break;
		case lss:
		    gen(opr,0,10);
		    break;
		case geq:
		    gen(opr,0,11);
		    break;
		case gtr:
		    gen(opr,0,12);
		    break;
		case leq:
		    gen(opr,0,13);
		    break;
	    }
	}
    }
}


//语句处理过程
//stmt -> ident := exp | call ident | begin stmt; stmt end | if then | while do| nul 
void statement(__int64 fsys){
    long i,cx1,cx2;

    if(sym==ident){
	i=position(id);
	if(i==0){
	    error(11);
	}else if(table[i].kind!=variable){
	    error(12); i=0;
	}
	getsym();
	if(sym==becomes){
	    getsym();
	}else{
	    error(13);
	}
	expression(fsys);
	if(i!=0){
	    gen(sto,lev-table[i].level,table[i].addr);
	}
    }else if(sym==callsym){
	getsym();
	if(sym!=ident){
	    error(14);
	}else{
	    i=position(id);
	    if(i==0){
		error(11);
	    }else if(table[i].kind==proc){
		gen(cal,lev-table[i].level,table[i].addr);
	    }else{
		error(15);
	    }
	    getsym();
	}
    }
	else if(sym==ifsym)
	{
		getsym(); 
		condition(fsys|thensym|dosym);
		if(sym==thensym)
		{
	    	getsym();
		}
		else
		{
	    	error(16);
		}
		cx1=cx;	
		gen(jpc,0,0);
		statement(fsys);
		if (sym == elsesym) 
		{
			getsym();
			cx2 = cx;
			gen(jmp, 0, 0);		// 无条件跳转到else之后
			code[cx1].a=cx;		// 不满足条件时，回填跳转地址为else处
			statement(fsys);
			code[cx2].a = cx;	// 回填跳过else后的地址
		} 
		else 
		{
			code[cx1].a = cx;	// 不是else语句时，回填跳转地址到then之后
		}
    }
	else if(sym==beginsym){
	getsym(); statement(fsys|semicolon|endsym);
	while(sym==semicolon||(sym&statbegsys)){
	    if(sym==semicolon){
		getsym();
	    }else{
		error(10);
	    }
	    statement(fsys|semicolon|endsym);
	}
	if(sym==endsym){
	    getsym();
	}else{
	    error(17);
	}
    }
		else if (sym == whilesym) {
		llev++;
		cx1 = cx; getsym();
		condition(fsys | dosym);
		cx2 = cx;	gen(jpc, 0, 0);
		if (sym == dosym) {
			getsym();
		}
		else {
			error(18);
		}
		statement(fsys); gen(jmp, 0, cx1);
		code[cx2].a = cx;
		if (excx != 0) {
			code[excx].a = cx;
			excx = 0;
		}
		llev--;		// 一层循环结束
	}
	else if (sym == exitsym) {
		if (llev == 0) {
			error(600);		// 循环外调用了exit
		}
		else {
			excx = cx;
			gen(jmp, 0, 0);		// 无条件跳转到循环结束
		}
		getsym();
	}
	else if (sym == readsym) 
	{
		getsym();
		if (sym != lparen) 
		{
			error(35);
		}                     //如果左括号则报错35号：read\write后面遗漏左右括号
		else {
			do { //如果读到逗号说明还有变量需要执行read/write操作
				getsym();
				if (sym == ident) //调用position函数根据id查找符号表table中对应结构体
					i = position(id);
				if (i == 0) error(36); //符号表中没有找到符号：read write后面的括号里应该是声明过的变量名
				else if (table[i].kind == constant || table[i].kind == proc)
				{
					error(12); i = 0;
					getsym();
					continue;
				} //如果是常量或者过程名不允许被赋值，此时跳过本次循环，继续读入单词并循环
				else {
					gen(opr, 0, 14); //说明赋值的是符号表中声明过的变量，生成指令 opr,0,14，14 在解释函数 interpret()中对应 read
					gen(sto, lev - table[i].level, table[i].addr); //*生成指令 sto 指令，将栈顶的值送到变量中
					getsym();//当前block的层差-变量的层差就是要回溯的层数
				}
			} while (sym == comma);
			if (sym == rparen)
				getsym();
			gen(opr, 0, 15); // 取得换行符
		}
	}
	else if (sym == writesym) {
		getsym();
		if (sym == lparen) {
			do { //当读到逗号说明还需要继续写
				getsym();
				expression(rparen|comma|fsys); //调用expression函数来分析表达式，rparen是:当语法分析进入或退出某一语法单元时当前单词符合应属于的集合,fsys在某一出错状态下，可恢复语法分析正常工作的补充单词集合  
				gen(opr, 0, 16); //生成输出指令，输出栈顶的整数 
			} while (sym == comma);
			if (sym != rparen) { //如果不是右括号：read\write后面遗漏左右括号
				error(35);
			}
			else
				getsym();
			gen(opr, 0, 17); //输出换行符
		}
		else
			error(35);
	}
    test(fsys,0,19);
}

//语法分析
void block(__int64 fsys){
    long tx0;		
    long cx0; 		
    long tx1;		
    long dx1;

    dx=3; tx0=tx; table[tx].addr=cx; gen(jmp,0,0);
    if(lev>levmax){
	error(32);
    }
    do{
	if(sym==constsym){
	    getsym();
	    do{
		constdeclaration();
		while(sym==comma){
		    getsym(); constdeclaration();
		}
		if(sym==semicolon){
		    getsym();
		}else{
		    error(5);
		}
	    }while(sym==ident);
	}
	if(sym==varsym){
	    getsym();
	    do{
		vardeclaration();
		while(sym==comma){
		    getsym(); vardeclaration();
		}
		if(sym==semicolon) {
		    getsym();
		}else{
		    error(5);
		}
	    }while(sym==ident);
	}
	while(sym==procsym){
	    getsym();
	    if(sym==ident){
		enter(proc); getsym();
	    }else{
		error(4);
	    }
	    if(sym==semicolon){
		getsym();
	    }else{
		error(5);
	    }
	    lev=lev+1; tx1=tx; dx1=dx;
	    block(fsys|semicolon);
	    lev=lev-1; tx=tx1; dx=dx1;
	    if(sym==semicolon){
		getsym();
		test(statbegsys|ident|procsym,fsys,6);
	    }else{
		error(5);
	    }
	}
	test(statbegsys|ident,declbegsys,7);
    }while(sym&declbegsys);
    code[table[tx0].addr].a=cx;
    table[tx0].addr=cx;		
    cx0=cx; gen(Int,0,dx);
    statement(fsys|semicolon|endsym);
    gen(opr,0,0);
    test(fsys,0,8);
    listcode(cx0);
}

//通过静态链求出数据区基地址的函数 
/* 参数说明：l:要求的数据区所在层与当前层的层差 */   
/* 返回值：要求的数据区基址 */
long base(long b, long l){
    long b1;
    b1=b;
    while (l>0){
	b1=s[b1]; l=l-1;
    }
    return b1;
}


/*解释过程*/
void interpret(){
    long p,b,t;		
    instruction i;	
	int a, j;
	double getnum = 0;
	char ch;
    printf("start PL/0\n");
    t=0; b=1; p=0;
    s[1]=0; s[2]=0; s[3]=0;
    do{
	i=code[p]; p=p+1;
	switch(i.f){
	    case lit:
		t=t+1; s[t]=i.a;
		break;
	    case opr:
		switch(i.a){ 	
		    case 0:
			t=b-1; p=s[t+3]; b=s[t+2];
			break;
		    case 1:
			s[t]=-s[t];
			break;
		    case 2:
			t=t-1; s[t]=s[t]+s[t+1];
			break;
		    case 3:
			t=t-1; s[t]=s[t]-s[t+1];
			break;
		    case 4:
			t=t-1; s[t]=s[t]*s[t+1];
			break;
		    case 5:
			t=t-1; s[t]=s[t]/s[t+1];
			break;
		    case 6:
			s[t]=s[t]%2;
			break;
		    case 8:
			t=t-1; s[t]=(s[t]==s[t+1]);
			break;
		    case 9:
			t=t-1; s[t]=(s[t]!=s[t+1]);
			break;
		    case 10:
			t=t-1; s[t]=(s[t]<s[t+1]);
			break;
		    case 11:
			t=t-1; s[t]=(s[t]>=s[t+1]);
			break;
		    case 12:
			t=t-1; s[t]=(s[t]>s[t+1]);
			break;
		    case 13:
			t=t-1; s[t]=(s[t]<=s[t+1]);
			break;
			case 14: //opr 包括一组算术和关系运算的指令。 //read指令
				getnum = 0; //用于暂时存储字符串转数字
				t++;//栈指针
				ch = getchar(); //读取输入内容，以空格分割
				while (ch != ' ' && ch != '.') {
					if (ch == '\n') ch = '0';
					getnum = getnum * 10 + (ch - '0'); //字符串转数字
					ch = getchar(); //读取下一个字符
				}
				s[t] = getnum; //放入栈中
				break;
			case 15:
				ch = getchar(); ///读取换行符
				break;
			case 16: //write指令
				printf("%5d", (long)s[t]); //输出栈顶
				t--;
				break;
			case 17:
				printf("\n"); //输出换行符
		}
		break;
	    case lod:
		t=t+1; s[t]=s[base(b,i.l)+i.a];
		break;
	    case sto://将栈顶的值写到变量内存中 //base：根据访问链往上回溯找到变量 返回访问链的下标
		s[base(b,i.l)+i.a]=s[t]; /*printf("%10d\n", s[t]);*/ t=t-1;//i/* 类 PCODE 指令类型，包含三个字段：指令 f、层差 l 和另一个操作数 a */ 
		break;
	    case cal:
		s[t+1]=base(b,i.l); s[t+2]=b; s[t+3]=p;
		b=t+1; p=i.a;
		break;
	    case Int:
		t=t+i.a;
		break;
	    case jmp:
		p=i.a;
		break;
	    case jpc:
		if(s[t]==0){
		    p=i.a;
		}
		t=t-1;
	}
    }while(p!=0);
    printf("end PL/0\n");
}

main(){
    long i;
    for(i=0; i<256; i++){
	ssym[i]=nul;
    }
    strcpy(word[0],  "begin     ");
    strcpy(word[1],  "call      ");
    strcpy(word[2],  "const     ");
    strcpy(word[3],  "do        ");
    strcpy(word[4],  "else      ");		// 需要有序排列
    strcpy(word[5],  "end       ");
    strcpy(word[6],  "exit      ");
    strcpy(word[7],  "if        ");
    strcpy(word[8],  "odd       ");
    strcpy(word[9],  "procedure ");
	strcpy(word[10],  "read      ");
    strcpy(word[11],  "then      ");
    strcpy(word[12], "var       ");
    strcpy(word[13], "while     ");
	strcpy(word[14], "write     ");
    wsym[0]=beginsym;
    wsym[1]=callsym;
    wsym[2]=constsym;
    wsym[3]=dosym;
    wsym[4]=elsesym;
    wsym[5]=endsym;
    wsym[6]=exitsym;
    wsym[7]=ifsym;
    wsym[8]=oddsym;
    wsym[9]=procsym;
	wsym[10] = readsym;
    wsym[11]=thensym;
    wsym[12]=varsym;
    wsym[13]=whilesym;
	wsym[14] = writesym;
    ssym['+']=plus;
    ssym['-']=minus;
    ssym['*']=times;
    ssym['/']=slash;
    ssym['(']=lparen;
    ssym[')']=rparen;
    ssym['=']=eql;
    ssym[',']=comma;
    ssym['.']=period;
    ssym[';']=semicolon;
    strcpy(mnemonic[lit],"lit");
    strcpy(mnemonic[opr],"opr");
    strcpy(mnemonic[lod],"lod");
    strcpy(mnemonic[sto],"sto");
    strcpy(mnemonic[cal],"cal");
    strcpy(mnemonic[Int],"int");
    strcpy(mnemonic[jmp],"jmp");
    strcpy(mnemonic[jpc],"jpc");
    declbegsys=constsym|varsym|procsym;
    statbegsys=beginsym|callsym|ifsym|whilesym|exitsym | writesym | readsym|elsesym;
    facbegsys=ident|number|lparen;
    printf("please input source program file name: ");
    scanf("%s",infilename);
    printf("\n");
    if((infile=fopen(infilename,"r"))==NULL){
	printf("File %s can't be opened.\n", infilename);
	exit(1);
    }
    
    err=0;
    cc=0; cx=0; ll=0; ch=' '; kk=al; getsym();
    lev=0; tx=0;
    block(declbegsys|statbegsys|period);
    if(sym!=period){
	error(9);
    }
    if(err==0){
		if ((outfile = fopen("out.txt", "wb")) == NULL) {
			printf("File <out.txt> can't be opened.\n");
			exit(1);
		}
		fwrite(&code, sizeof(instruction), cxmax, outfile);
		fclose(outfile);
		if ((outfile = fopen("code.txt", "w")) == NULL) {
			printf("File <out.txt> can't be opened.\n");
			exit(1);
		}
		for (i = 0; i <= cx; i++) {
			fprintf(outfile, "%10d%5s%3d%10.5f\n", i, mnemonic[code[i].f], code[i].l, code[i].a);
		}
		fclose(outfile);
	interpret();
    }else{
	printf("errors in PL/0 program\n");
    }
    fclose(infile);
	return(0);
}
